/*
实验2-6 判断两个广义表是否相等
分数 25
作者 陈越
单位 浙江大学

请设计一个算法判断两个广义表是否相等。
函数接口定义：

bool IsEqual( GList glist1, GList glist2 );

其中广义表 GList 的定义如下：

typedef enum { element, sublist } ElemTag; /* 结点标记类型
typedef struct GListNode *Position;        /* 指针即结点位置
typedef Position GList;
struct GListNode {
    ElemTag tag;        /* 结点标记
    union {
        ElemSet data;   /* 存储数据
        GList sub_list; /* 子表
    } u;
    Position next;      /* 线性表中下一个元素的位置
};

函数接口定义中，ElemSet 是用户定义的数据类型，例如 int、double 或者 char
等。函数 IsEqual 需要判断两个给定的广义表 glist1 和 glist2
是否完全相同。若相同则返回 true，否则返回 false。

输入样例 1：

3
2
0 1
0 2
2
0 3
0 4
0 5
3
2
0 1
0 2
2
0 3
0 4
0 5

输出样例 1：

true

输入样例 2：

3
2
0 1
0 2
2
0 3
0 4
0 5
3
2
0 1
0 2
2
0 3
0 0
0 5

输出样例 2：

false
*/

#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int ElemSet;
typedef enum { element, sublist } ElemTag; /* 结点标记类型 */
typedef struct GListNode *Position;        /* 指针即结点位置 */
typedef Position GList;
struct GListNode {
    ElemTag tag; /* 结点标记 */
    union {
        ElemSet data;   /* 存储数据 */
        GList sub_list; /* 子表 */
    } u;
    Position next; /* 线性表中下一个元素的位置 */
};

GList BuildList(int n) { /* 创建主线上有n个结点的广义表 */
    int k, i;
    GList list, tail, tmp;

    list = (GList)malloc(sizeof(struct GListNode)); /* 创建临时空头结点 */
    list->next = NULL;
    tail = list; /* 初始化尾指针 */
    for (i = 0; i < n; i++) {
        tmp = (GList)malloc(sizeof(struct GListNode));
        scanf("%d", &k);
        if (k == 0) { /* 当前结点是数据 */
            tmp->tag = element;
            scanf("%d", &tmp->u.data);
        } else { /* 当前结点是子表 */
            tmp->tag = sublist;
            tmp->u.sub_list = BuildList(k); /* 递归创建子表 */
        }
        /* 将当前结点插入链表尾 */
        tail->next = tmp;
        tmp->next = NULL;
        tail = tmp;
    }
    tmp = list;
    list = tmp->next;
    free(tmp); /* 删除临时头结点 */
    return list;
}

bool IsEqual(GList glist1, GList glist2);

int main(void) {
    GList glist1, glist2;
    int n;

    scanf("%d", &n);
    glist1 = BuildList(n);
    scanf("%d", &n);
    glist2 = BuildList(n);
    if (IsEqual(glist1, glist2) == true) {
        printf("true");
    } else {
        printf("false");
    }

    return 0;
}
/* 你的代码将被嵌在这里 */

bool IsEqual(GList glist1, GList glist2) {
    Position p1, p2;
    p1 = glist1;
    p2 = glist2;
    while (p1 && p2) {
        if (p1->tag != p2->tag) {
            return false;
        }
        if (p1->tag == element && p2->tag == element) {
            if (p1->u.data != p2->u.data) {
                return false;
            }
        } else if (p1->tag == sublist && p2->tag == sublist) {
            if (!IsEqual(p1->u.sub_list, p2->u.sub_list)) {
                return false;
            }
        } else {
            return false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    if (p1 || p2) {
        return false;
    }
    return true;
}